Slists are data structures that are lockless implementations of a LIFO (last in first out) list made available in operating systems. Slists are typically a desired choice of data structure to hold fixed size buffers that can be allocated and released without holding any spinlocks or other synchronization primitives. Slists may also be used for variable sized contents in the form of a lockless singly linked list. Other capabilities are provided in an operating system environment—such as lookaside lists which are built on Slists.
However, in some scenarios, the use of Slists may not be desirable. For one example, a single Slist header may become a cache line contention hotspot on servers with many processors accessing the same Slist. This may be a scalability bottleneck in both native and Hyper-V virtualized scenarios.
In another scenario, Slists are mainly used as packet caches or fixed size buffer repositories. However there are scenarios where more complex data structures or resources of possibly varying sizes have to be maintained in such a lockless list. It may be desired to have more operations than just ‘Push’ and ‘Pop’ for purposes such as load balancing, packet stealing, NUMA awareness and such other algorithmic requirements. These are often satisfied by another data structure abstraction to manage multiple Slists. Lookaside lists are one such example.
Lookaside lists maintain a cache of fixed size buffers for speedy memory allocation and release. For processor affinity benefits, some operating systems also provide per-processor lookaside lists. These per-processor lookaside lists are generally (but not necessarily) backed by a global list to contain backup packets in case the per-processor list is empty. It may be desired to have extra resource allocations to have a fairly big global backup list to provide an abstraction of a single resource pool. When demand recedes, these extra memory allocations may be freed if there is demand for the memory. However, in certain scenarios resources cannot be over-allocated. This is particularly true for hardware drivers that define limits of their capacity—like maximum number of I/O requests a RAID controller can process. Advance algorithms tie these limits to Slist depths and avoid using spinlocks. Also extra overhead of allocs and frees cause memory fragmentation and costs CPU cycles. Lookaside lists that allocate more than the requisite quantity may not be used for these reasons.